The present invention relates to the field of computer graphics. Many computer graphic images are created by mathematically modeling the interaction of light with a three dimensional scene from a given viewpoint. This process, called rendering, generates a two-dimensional image of the scene from the given viewpoint, and is analogous to taking a photograph of a real-world scene.
Realistic and dynamic shadows are crucial for rendering high-quality computer graphics. Shadow volume rendering is one technique for generating shadows. A shadow volume defines a region of space that is in the shadow of a particular object (referred to as an occluder) with respect to a particular light source. Using shadow volumes turns the problem of rendering shadows from a lighting problem to a geometry problem. A shadow test determines whether all or a portion of an object is inside the shadow volume defined by an occluder and a light source. If all or a portion of an object is inside the shadow volume, then these portions are shadowed with respect to the particular light source. Conversely, if all or a portion of an object is outside the shadow volume of the occluder, as well all other occluder shadow volumes, then these portions are illuminated by the light source. The shadow test is repeated for each object and for every light source (and corresponding shadow volume) in a scene. The shadow test can be performed on a per-pixel basis or on a group of pixels in parallel.
As the demand for computer graphics, and in particular for real-time computer graphics, has increased, specialized hardware for accelerating the rendering process has become widespread. Hardware stencil buffers can be used to improve the performance of shadow volume algorithms. Stencil buffers can mask off portions of the rendered image in shadow from a particular light source. The unmasked portions of the rendered image are then re-rendered to add the illumination from the light source.
Due to the limitations of memory speed and bandwidth, pixel fill rate, which is the number of pixels that the graphics hardware can update in a given time period, is a critical bottleneck in graphics hardware performance. Because the computation of the mask in the stencil buffer requires rasterizing numerous shadow volume primitives and extensive reading and writing to the stencil buffer, rendering shadow volumes consumes tremendous amounts of pixel fill rate. This makes rendering dynamic shadows time-consuming and real-time rendering difficult for complex scenes.
It is desirable for computer graphics hardware to reduce the number of stencil buffer updates needed to render shadow volumes, thereby decreasing the pixel fill rate requirements and improving performance. It is further desirable that any optimization of shadow volume rendering requires little modification of the rendering application and results in correct images without artifacts or errors. Additionally, it is desirable for computer graphics hardware to reduce the number of stencil buffer updates needed to render other types of volumes, such as fog, smoke, constructive solid geometry, or collision detection.